package com.lnn.algorithm.sa;

import com.lnn.pojo.Node;
import com.lnn.pojo.Route;
import com.lnn.util.Address;
import com.lnn.util.Matrix;
import lombok.Data;
import org.springframework.web.multipart.MultipartFile;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Objects;
import java.util.Random;

/**
 * 模拟退火算法实现类
 *
 * @author: Li Ning Ning
 * @time: 2021/7/26 16:06
 * @description: TODO
 * @version: 1.0
 */
@Data
public class SA {

    /**
     * 城市数量
     */
    private int cityNum;

    /**
     * 每个温度迭代次数
     */
    private int iterMax;

    /**
     * 初始温度
     */
    private double t0;

    /**
     * 终止温度
     */
    private double tf;

    /**
     * 降温系数
     */
    private double alpha;

    /**
     * 距离矩阵
     */
    private int[][] distance;

    /**
     * 最佳出现代数
     */
    private int bestIter;

    /**
     * 随机数
     */
    private Random random;

    /**
     * 当前路径
     */
    private int[] route;

    /**
     * 当前路径长度
     */
    private int routeLength;

    /**
     * 最佳路径
     */
    private int[] bestRoute;

    /**
     * 最佳长度
     */
    private int bestRouteLength;

    /**
     * 最佳路径地址
     */
    private String[] address;

    /**
     * 城市坐标x
     */
    private int[] x;

    /**
     * 城市坐标y
     */
    private int[] y;

    public SA() {

    }

    public SA(int iterMax, double t0, double tf, float alpha) {
        this.iterMax = iterMax;
        this.t0 = t0;
        this.tf = tf;
        this.alpha = alpha;
    }

    public SA(int cityNum, int iterMax, double t0, double tf, float alpha) {
        this.cityNum = cityNum;
        this.iterMax = iterMax;
        this.t0 = t0;
        this.tf = tf;
        this.alpha = alpha;
    }

    /**
     * 初始化参数
     *
     * @param distance 距离矩阵
     * @param address  位置数组
     */
    public SA init(int[][] distance, String[] address) {
        //初始化距离矩阵
        this.distance = distance;
        //初始化地址
        this.address = address;
        //初始化参数
        initParams();
        return this;
    }

    /**
     * 文件初始化参数
     */
    public SA init(MultipartFile multipartFile) throws IOException {
        // 读取数据
        File file = new File(Objects.requireNonNull(multipartFile.getOriginalFilename()));
        readFile(multipartFile, file);

        String strBuff;
        BufferedReader data = new BufferedReader(new InputStreamReader(
                new FileInputStream(file)));
        //初始化城市总数
        String temp = data.readLine();
        this.cityNum = Integer.parseInt(temp);
        distance = new int[cityNum][cityNum];
        x = new int[cityNum];
        y = new int[cityNum];
        address = new String[cityNum];
        for (int i = 0; i < cityNum; i++) {
            address[i] = "Node" + i;
        }
        //初始化城市坐标
        for (int i = 0; i < cityNum; i++) {
            strBuff = data.readLine();
            String[] strCol = strBuff.split(" ");
            x[i] = Integer.parseInt(strCol[1]);
            y[i] = Integer.parseInt(strCol[2]);
        }
        // 计算距离矩阵
        this.distance = Matrix.computeDistanceMatrix(x, y);
        initParams();
        return this;
    }

    private void readFile(MultipartFile multipartFile, File file) {
        int n;
        try (InputStream in = multipartFile.getInputStream(); OutputStream os = new FileOutputStream(file)) {
            // 得到文件流。以文件流的方式输出到新文件
            byte[] buffer = new byte[4096];
            while ((n = in.read(buffer, 0, 4096)) != -1) {
                os.write(buffer, 0, n);//写入文件
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 初始化参数
     */
    private void initParams() {
        //初始化路径
        route = new int[cityNum + 1];
        //初始化路径长度
        routeLength = Integer.MAX_VALUE;
        //初始化最优路径
        bestRoute = new int[cityNum + 1];
        //初始化最优路径长度
        bestRouteLength = Integer.MAX_VALUE;
        //初始化最优迭代次数
        bestIter = 0;
        //初始化随便变量
        random = new Random(System.currentTimeMillis());
    }

    /**
     * 多次迭代路径
     *
     * @return 路径列表
     */
    public ArrayList<Route> solve() {
        //初始化路径
        initRoute();
        //计算初始路径长度
        routeLength = evaluate(route);
        //保存初始路径到前最好路径
        bestRoute = Arrays.copyOf(route, route.length);
        //保存最好路径长度
        bestRouteLength = routeLength;
        int k = 0;// 降温次数
        double t = t0;
        while (t > tf) {
            int iter = 0; //每次降温迭代
            while (iter < iterMax) {
                int[] neighbourRoute = generateNeighbour(route);// 得到当前编码initRout的邻域编码tempRout
                int neighbourRouteLength = evaluate(neighbourRoute);
                if (neighbourRouteLength < bestRouteLength) {
                    bestRoute = Arrays.copyOf(neighbourRoute, neighbourRoute.length);
                    bestRouteLength = neighbourRouteLength;
                }
                if (neighbourRouteLength < routeLength
                        || Math.exp((routeLength - neighbourRouteLength) / t) > random.nextDouble()) {
                    route = Arrays.copyOf(neighbourRoute, neighbourRoute.length);
                    routeLength = neighbourRouteLength;
                }
                iter++;
                bestIter = k;
            }
            t = alpha * t;
            k++;
        }
        ArrayList<Route> routes = formatData();
        printOptimal();
        return routes;
    }

    /**
     * 初始化路径
     */
    private void initRoute() {
        int j;
        route[0] = random.nextInt(65535) % cityNum;
        for (int i = 1; i < cityNum; ) {
            route[i] = random.nextInt(65535) % cityNum;
            for (j = 0; j < i; j++) {
                if (route[i] == route[j]) {
                    break;
                }
            }
            if (j == i) {
                i++;
            }
        }
    }

    /**
     * 计算路径长度
     *
     * @param route 路径
     * @return 路径长度
     */
    private int evaluate(int[] route) {
        int len = 0;
        for (int i = 1; i < cityNum; i++) {
            len += distance[route[i - 1]][route[i]];
        }
        len += distance[route[cityNum - 1]][route[0]];
        return len;
    }

    /**
     * 随机交换两个城市的位置
     */
    private int[] generateNeighbour(int[] route) {
        int[] res = Arrays.copyOf(route, route.length);
        int random1 = random.nextInt(65535) % cityNum;
        int random2 = random.nextInt(65535) % cityNum;
        while (random1 == random2) {
            random2 = random.nextInt(65535) % cityNum;
        }
        int temp = res[random1];
        res[random1] = res[random2];
        res[random2] = temp;
        return res;
    }

    private ArrayList<Route> formatData() {
        bestRoute = Address.StartAtZero(bestRoute);
        address = Address.arrayToAddress(bestRoute, address);
        ArrayList<Route> routes = new ArrayList<>();
        for (int i = 0; i < bestRoute.length; i++) {
            Route route = new Route();
            route.setNumber(bestRoute[i]);
            route.setAddress(address[i]);
            route.setDistance(distance[bestRoute[i]][bestRoute[(i + 1) % bestRoute.length]]);
            route.setTotalCity(address.length - 1);
            route.setTotalDistance(bestRouteLength);
            if (x != null && y != null) {
                route.setNode(new Node(x[bestRoute[i]], y[bestRoute[i]]));
            }
            routes.add(route);
        }
        return routes;
    }

    private void printOptimal() {
        System.out.println("模拟退火算法: ");
        System.out.println("The optimal length is: " + bestRouteLength);
        System.out.println("The optimal tour is: ");
        for (int i = 0; i < cityNum + 1; i++) {
            System.out.print(bestRoute[i] + " ");
        }
        System.out.println();
    }
}
